// LeetCode 主站 Problem Nr. 650: 只有两个键的键盘

/*
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
    Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
    Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

示例 1：

	输入：3
	输出：3
	解释：
	最初, 只有一个字符 'A'。
	第 1 步, 使用 Copy All 操作。
	第 2 步, 使用 Paste 操作来获得 'AA'。
	第 3 步, 使用 Paste 操作来获得 'AAA'。

示例 2：
	输入：n = 1
	输出：0

提示：
    1 <= n <= 1000
*/

package main

import (
	"fmt"
	"math"
)

func minSteps(n int) int {
	return method1(n)
}

func method1(n int) int {
	f := make([]int, n+1)
    for i := 2; i <= n; i++ {
        f[i] = math.MaxInt32
        for j := 1; j*j <= i; j++ {
            if i%j == 0 {
                f[i] = min(f[i], f[i/j]+j, f[j]+i/j)
            }
        }
    }
    return f[n]
}

func min(numbers ...int) int {
	result := numbers[0]
    for _, number := range numbers {
        if number < result {
            result = number
        }
    }
    return result
}

func main() {
	for i := 1; i <= 10; i++ {
		fmt.Println(minSteps(i))
	}

	a, b := 5.0, 2.0
	fmt.Println(int(a/b))
}
